package leetcode;

public class Day30 {
    public void insertSort(int[] arr){
        for (int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for (;j>=0;j--){
                if (arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else break;;
            }
            arr[j+1]=tmp;
        }
    }
    public void quickSort(int start,int end,int[] arr){
        if(start>=end){
            return;
        }
        int piov=toSort(start,end,arr);
        quickSort(start,piov-1,arr);
        quickSort(piov+1,end,arr);
    }

    private int toSort(int start, int end, int[] arr) {
        int tmp=arr[start];
        int l=start;
        while (start<end){
            while (start<end&&arr[start]<tmp){
                start++;
            }
            while (start<end&&arr[end]>tmp){
                end--;
            }
            Swap(start,end,arr);
        }
        Swap(l,end,arr);
        return start;
    }

    private void Swap(int start, int end, int[] arr) {
        int tmp=arr[start];
        arr[start]=arr[end];
        arr[end]=tmp;
    }
    public void mergeSort(int[] arr){
        mergeFun(0,arr.length-1,arr);
    }

    private void mergeFun(int l, int r, int[] arr) {
        if(l>=r){
            return;
        }
        int mid=(l+r)/2;
        mergeFun(l,mid,arr);
        mergeFun(mid+1,r,arr);
        merge(l,r,mid,arr);
    }

    private void merge(int l, int r, int mid, int[] arr) {
        int s1=l;
        int e1=mid;
        int s2=mid+1;
        int e2=r;
        int[] ret=new int[r-l+1];
        int i=0;
        while (s1<=e1&&s2<=e2){
            if(arr[s1]<arr[s2]){
                ret[i]=arr[s1];
                i++;
                s1++;
            }else {
                ret[i]=arr[s2];
                i++;
                s2++;
            }
        }
        while (s1<=e1){
           ret[i]=arr[s1];
           i++;
           s1++;
        }
        while (s2<=e2){
            ret[i]=arr[s2];
            i++;
            s2++;
        }
        for (int j=0;j<ret.length;j++){
            arr[j+l]=ret[j];
        }
    }
    /*
    * 堆排序
    * */
    public void heapSort(int[] arr){
        creatheap(arr);
        int end=arr.length-1;
        while (end>0){
            Swap(0,end,arr);
            end--;
            shiftdown(0,arr.length,arr);
        }
    }
    private void creatheap(int[] arr) {
        int parent=(arr.length-1-1)/2;
        for (;parent>=0;parent--){
            shiftdown(parent,arr.length,arr);}}
    private void shiftdown(int parent, int size, int[] arr) {
        int child=2*parent+1;
        while (child<size){
            if(child+1<size&&arr[child+1]>arr[child]){
                child=child+1;
            }
            if(arr[parent]<arr[child]){
                Swap(child,parent,arr);
                parent=child;
                child=2*parent+1;
            }else break;
        }

    }
}
